package com.demo2_两数相加.text3_链表;
/*
     需求: 给你两个非空 的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0开头。  2 -> 3 -> 4    4 -> 5 -> 6   实际是 432+654

    思路: 直接两个链表的数字相加, 加到长的链表上.
    1.先对两个链表进行长度的判断
    2.利用while循环将每个结点的值进行添加,添加到长链表的每一个结点.

    java 中指针和C语言里面一样儿的,指向同一个地方的内容所有的指针,都可以修改该内容. 链表优化

 */


public class Test3 {
    public static void main(String[] args) {

        ListNode listNode2 = new ListNode(9, null);
        ListNode listNode1 = new ListNode(9, listNode2);
        ListNode listNode = new ListNode(1, listNode1);
        System.out.println("链表一:");
        System.out.println(listNode);

        ListNode listNode5 = new ListNode(9, null);
        ListNode listNode4 = new ListNode(5, listNode5);
        ListNode listNode3 = new ListNode(4, listNode4);

        System.out.println("链表二:");
        System.out.println(listNode3);
        //创建对象
        Solution ss = new Solution();
        ListNode listNode6 = ss.addTwoNumbers(listNode, listNode3);
        System.out.println(listNode6);


    }
}

//解决方法
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //1.求2个链表的长度,并求出较大者.
        int length1 = getLength(l1);
        int length2 = getLength(l2);

        ListNode longNode = l1;
        ListNode shortNode = l2;
        if (length1 < length2) {
            longNode = l2;
            shortNode = l1;
            int temp=length1;
            length1=length2;
            length2=temp;
        }
        //2.长度相等
        if (length1 == length2) {
            ListNode tempNode1 = longNode;
            ListNode tempNode2 = shortNode;
            int sum;
            for (int i = 1; i <= length2; i++) {
                sum = tempNode1.val + tempNode2.val;
                tempNode1.val = sum % 10;
                //如果sum>=10 ,且不是最后一位,则向后进位,
                if ((sum >= 10) && (i < length2)) {
                    tempNode1.next.val += sum / 10;
                }
                //如果sum>=10 ,且是最后一位,则先创建一个新的结点,向后进位,
                if ((sum >= 10) && (i == length2)) {
                    tempNode1.next = new ListNode(sum / 10, null);
                }
                //指针向后移动
                tempNode1 = tempNode1.next;
                tempNode2 = tempNode2.next;
            }
            return longNode;
        }
        //3.长度不等,多出来的部分,特别计算
        if (length1 > length2) {
            ListNode tempNode1 = longNode;
            ListNode tempNode2 = shortNode;
            int sum;
            for (int i = 1; i <= length2; i++) {
                sum = tempNode1.val + tempNode2.val;
                tempNode1.val = sum % 10;
                //如果sum>=10 ,且不是最后一位,则向后进位,
                if (sum >= 10) {
                    tempNode1.next.val += sum / 10;
                }
                //指针向后移动
                tempNode1 = tempNode1.next;
                tempNode2 = tempNode2.next;
            }

            // 此处多出来的地方还是要继续for循环,因为可能是 长出来的部分是 999 的情况,+1, 会一直进位.
            for (int i = length2+1; i <=length1 ; i++) {
                int num=tempNode1.val;

                if (num<10){
                    break;
                }
                if((num>=10)&&(i<length1)){
                    tempNode1.val=num%10;
                    tempNode1.next.val+=num/10;
                    tempNode1=tempNode1.next;
                }
                if((num>=10)&&(i==length1)){
                    tempNode1.val=num%10;
                    tempNode1.next=new ListNode(num/10,null);
                }
            }
            return longNode;
        }
        return null;
    }
    //1.求链表长度
    public int getLength(ListNode listNode) {
        int count = 0;
        while (listNode != null) {
            count++;
            listNode = listNode.next;
        }
        return count;
    }
}

class ListNode {
    int val;  //  值
    ListNode next; // 下一个结点

    //空参构造
    ListNode() {

    }

    //带参构造
    ListNode(int val) {
        this.val = val;
    }

    //两种带参构造
    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }
}